package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 19:43 2020/8/12
 * @Description
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 * 输入: coins = [1, 2, 5], amount = 11
        输出: 3
        解释: 11 = 5 + 5 + 1
 */

import java.util.Arrays;

public class CoinChange {

    /**
     * 记忆化搜索法，与动态规划相反，从上而下
     * coinChange(amount) = min(coinChange(amount-coin))+1
     */

    /**
     * 不要看到最小就想到贪心，如果硬币金额为10,5,1则可以使用贪心，如果是随机就不能使用贪心
     * 此题应该使用动态规划来解决或者是递归（记忆化搜索）
     * 1.动态规划  最优子问题
     * if amount == 0 return 0
     * dp fill为 amount+1
     * if coin == i dp[i]=1
     * else if(i-coin>=0) dp[i]=min(dp[i-coin]+1,dp[i])
     * return dp[amount]>amount?-1:dp[amount]
     * 优化：
     * dp fill amount+1
     * dp[0]=0 也可以保证amount为0时不会出错 也可以对后面代码进行精简
     * if i>=coin  dp[i] = min(dp[i],dp[i-coin]+1)  若i==coin时，就为dp[0]+1=1优化了代码
     * return dp[amount]>amount?-1:dp[amount]
     */
/*    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
*/


    /**
     * 记忆化搜索就是递归的一个过程，就是对递归的优化方案
     * if memo[amount] != 0   return memo[amount]
     * doChange(amount) = min for(ans = doChange(amount-coin)))
     * if(ans>0&&ans<min) min = ans+1   memo[amount] = min
     * if min == amount+1 return -1  else retrun  memo[amount];
     */
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        memo = new int[amount + 1];
        return doChange(coins, amount);

    }

    private int doChange(int[] coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        //记忆化的过程
        if (memo[amount] != 0) {
            return memo[amount];
        }
        int min = amount + 1;
        for (int coin : coins) {
            int ans = doChange(coins, amount - coin);
            if (ans >= 0 && ans < min) {
                min = ans + 1;
            }
        }
        memo[amount] = min > amount ? -1 : min;
        return memo[amount];
    }

}
